//
// Created by YeMingMing on 2024-03-06.
//


// 约瑟夫环问题

#include <stdio.h>
#include <stdlib.h>

// 解决约瑟夫环问题
int josephus(int n, int k) {
    int i, idx = 0;
    int *people = (int *)malloc(n * sizeof(int));
    if (people == NULL) {
        printf("内存分配失败\n");
        return -1;
    }

    // 初始化数组，每个位置代表一个人，值为1表示在圈内，0表示已经被移除
    for (i = 0; i < n; i++)
        people[i] = 1;

    // 约瑟夫环的规则是每数到k就移除一个人，直到只剩下一个人
    for (i = 0; i < n - 1; i++) {
        int count = 0;
        while (count < k) {
            if (people[idx] == 1) {
                count++;
            }
            if (count < k) {
                idx = (idx + 1) % n; // 移动到下一个位置
            }
        }
        people[idx] = 0; // 移除当前位置的人
    }

    // 找到最后剩下的那个人
    for (i = 0; i < n; i++) {
        if (people[i] == 1) {
            return i + 1; // 返回这个人的位置
        }
    }
    return -1; // 如果出现异常，返回-1
}

int main() {
    int n, k;
    printf("请输入约瑟夫环的人数和间隔数：\n");
    scanf("%d %d", &n, &k);
    int survivor = josephus(n, k);
    printf("最后剩下的人在位置 %d\n", survivor);
    return 0;
}
